package link;

import beans.ListNode;

/**
 * @author pengfei.hpf
 * @date 2020/3/8
 * @verdion 1.0.0
 * 148. 排序链表
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 *
 * 示例 1:
 *
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 *
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 */
public class SortList {
    //TODO: 排序链表, 有空再写写?
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = slow.next;
        slow.next = null;
        ListNode first = sortList(head);
        ListNode second = sortList(fast);
        return merge(first, second);

    }

    private ListNode merge(ListNode head1, ListNode head2){
        ListNode head =  new ListNode(-1);
        ListNode node = head;
        while(head1 != null && head2 != null){
            if(head1.val <= head2.val){
                node.next = head1;
                head1 = head1.next;
            } else {
                node.next = head2;
                head2 = head2.next;
            }
            node = node.next;
        }
        if(head1 != null){
            node.next = head1;
        } else {
            node.next = head2;
        }
        return head.next;
    }
}
